To interlace or not to interlace has been a contentious issue between the television and computer communities. To the general public, there appears to be little difference between the television set and the computer monitor. However, those skilled in the art appreciate the fundamental difference of the video data formats in television and in computer monitors. Current television technology uses an interlaced scanning method. In this approach images are divided into several frames. Each frame is handled like a two-dimensional matrix; for US NTSC signals each frame has 525 lines. At each consecutive time, only one half of the lines are drawn, skipping every other line. Then the remaining lines are drawn, interlacing with the previous one. Computer monitors, on the other hand, use a progressive scanning approach that scans all the lines in order from top to bottom in a single frame.
At first, interlaced scanning was used because of some of its technological and psychophysical advantages. Interlacing was an efficient method to reduce bandwidth when TV frame memories were expensive and TV broadcast bandwidth was limited. Interlacing also takes advantage of psychophysical properties of human visual system. For example, the human visual system is less sensitive to flickering details than to large area flicker. Doubling the scanning frequency reduces the large area flickering. By only transmitting half of the information at a time, a higher scanning frequency can be achieved using the same bandwidth, which is one of interlacing's principal advantages. However, in addition to the loss of vertical resolution, interlacing results in many well-known artifacts such as line flicker. Line flicker happens when high vertical spectrum components in static images are present. It also produce vertical-temporal aliasing in moving images, if there is no appropriate vertical band limitation. Another major flaw of interlacing is that it complicates many images processing tasks, especially scanning format conversion.
Even though it seems that both interlaced scanning and progressive scanning each have a well-established area, with the advancement of the technology, especially in multimedia area, the demand for television video and personal computer video to converge is becoming irresistible. With the emergence of the new High Definition Television (HDTV) technology, a good algorithm for interlace-to-progressive scan conversion is becoming even more important, since many of the HDTV proposals either involve transmission of interlaced video, or high spatial frequency information at a reduced temporal rate. The consumer wants to be able to view a standard NTSC signal from broadcast or VCR in the new HDTV, but because of the nature of HDTV, the artifacts in a standard NTSC signal are becoming more visible and annoying when displayed on in high-definition television video. On the other hand, consumers also want to utilize their HDTV up to the maximum potential. A good interlace-to-progressive scan algorithm is needed to convert a standard NTSC signal to an HDTV signal.
Interlace-to-progressive scan conversion (which is sometimes called deinterlacing) can be described as interpolating the missing lines of an interlaced sequence. It can also be seen as a resolution enhancement technique, which can use either linear or non-linear interpolation (or both), or as a process to recover the alias component. If the interlacing process is seen as a form of spatio-temporal sub-sampling then interlace-to-progressive scan conversion is the reverse operation aiming at the removal of the sub-sampling artifact. From the mathematical perspective, the process of interlace-to-progressive scan conversion is a problem in linear up-sampling conversion.
A number of different interlace-to-progressive conversion algorithms have been proposed in the last few years. These algorithms range from simple spatial, temporal, or spatio-temporal conversion algorithms or filtering, to more advance motion adaptive filtering, to the most advanced adaptive conversion algorithm with motion estimation. Despite years of research, most of the algorithms are only suitable for specific image characteristics. In each case, the spectral content of the video data is different and hence requires different approaches. The challenge, therefore, is to implement an algorithm that can be adapted to various image characteristics. Unfortunately this is not a simple problem since interlace-to-progressive scan conversion, suffers from some fundamental problems. For example, though a few algorithms can adapt to various image characteristics, most of them are too complicated to implement in real applications.
In interlaced scanning, each frame is divided into two fields. The field is normally divided into top and bottom fields, the top field having the odd lines and the bottom having the even lines. These two fields are transmitted alternately. For the purposes of this paper the terms top and bottom field will be used for normal discussion, while odd and even fields with starting line equal to 1 is used whenever relation between frame/field number and line in the frame/field should be emphasized.
FIG. 1 illustrates the interlace-to-progressive scan conversion, or deinterlacing, task. The input video fields, containing samples of either the top or bottom vertical grid positions (lines) of an image, have to be converted to frames. These frames represent the same image as the corresponding                                           F            o                    ⁡                      (                          x              ,              y              ,              t                        )                          =                  {                                                                                          F                    ⁡                                          (                                              x                        ,                        y                        ,                        t                                            )                                                        ,                                                                              (                                                            y                      ⁢                                                                                           ⁢                      mod                      ⁢                                                                                           ⁢                      2                                        =                                          t                      ⁢                                                                                           ⁢                      mod                      ⁢                                                                                           ⁢                      2                                                        )                                                                                                                                                F                      i                                        ⁡                                          (                                              x                        ,                        y                        ,                        t                                            )                                                        ,                                                                                                ⁢                                      (                    otherwise                    )                                                                                                          (        1.0        )            input field but contain the samples of all lines. Formally, the output frame Fo(x,y,t) can be defined as:                where: F(x, y, t) is the pixels from the original line from the input field        x, y are coordinates in the spatial plane,        t is coordinate in temporal domain        Fl(x,y,t) is the interpolated pixels        
The interlace-to-progressive scan conversion process doubles the frequency in vertical space. The process removes the first repeated spectrum caused by the interlaced sampling of the video. At first interlace-to-progressive scan conversion seems like an easy task. However, due to lack of prefiltering in the interlacing process, the interlace-to-progressive scan conversion process is not as simple as it looks like.
There are two major problems confronting interlace-to-progressive scan conversion processes. The first is that TV signals do not fulfill the demands of the sampling theorem, i.e., it doesn't satisfy the Nyquist criteria. Interlaced scanning introduces aliasing, unless the moving image is properly pre-filtered with a low pass filter. In actual image capturing devices, temporal filtering is performed by camera time integration, and is performed independently of spatial filtering, resulting in separable prefiltering. In most practical systems, there is no prefiltering to suppress the higher frequencies prior to sampling in TV signals. Hence, some of the information is lost during the interlaced sampling process. From frequency domain point of view, some of the higher frequencies still lie outside the sampling frequency, and thus cause aliasing.
The second major problem is that the temporal frequencies at the retina of an observer have an unknown relation to the scene content. The results from psychophysical experiments shows that temporal filtering blurs moving objects due to eye tracking. High frequencies due to object motion are mapped to zero frequency (DC) at the retina if the observer tracks the object. Consequently, suppression of such apparently high and less relevant frequencies results in significant blurring for this viewer. Due to this complication the apparent quality of interlaced video is best if it comes from progressive video by dropping half the lines with motion adaptive prefiltering. In most cases, motion adaptive prefiltering is not feasible, and interlacing is done without any prefiltering.
FIG. 2a shows the vertical temporal (VT) video spectrum of a static scene. This spectrum includes baseband and spectral replicas due to the interlaced sampling. The sampling lattices result in a quincunx pattern of the centers of the spectral replicas. The vertical detail of the scene determines the extent of the VT spectrum support, while vertical motion changes its orientation, as illustrated in FIG. 2b. FIG. 3a illustrates the general spectrum for an interlaced signal with motion, and FIG. 3b shows the ideal spectrum result from an interlace-to-progressive scan conversion process. Clearly, interlace-to-progressive scan conversion is a spatio-temporal problem.
Over the last 30 years researchers have proposed many different algorithms for interlace-to-progressive scan conversion. So far no one has discovered an algorithm that can perfectly deinterlace every image sequence. One major division among these algorithms is motion compensation.
Most of the algorithms that were introduced before 1990 used motion non-compensated methods. They fall generally into the categories of linear and non-linear methods. Linear methods are the best methods in the absence of motion. These methods are considered outdated within the TV-product community. However they are still widely used in the computer community, especially for multimedia products.
Linear methods are well-known for their low cost of implementation. All linear methods, whether using spatial, temporal, or spatio-temporal filtering can be defined by:                                           F            o                    ⁡                      (                          x              ,              y              ,              t                        )                          =                  {                                                                                                                                      ⁢                                                                        F                          ⁡                                                      (                                                          x                              ,                              y                              ,                              t                                                        )                                                                          ,                                                                                                                        (                                                                        y                          ⁢                                                                                                           ⁢                          mod                          ⁢                                                                                                           ⁢                          2                                                =                                                  t                          ⁢                                                                                                           ⁢                          mod                          ⁢                                                                                                           ⁢                          2                                                                    )                                                                                                                                                                                    ∑                          k                                                ⁢                                                                                                   ⁢                                                                              F                            ⁡                                                          (                                                              x                                ,                                                                  y                                  +                                  k                                                                ,                                                                  t                                  +                                  n                                                                                            )                                                                                ⁢                                                      h                            ⁡                                                          (                                                              k                                ,                                n                                                            )                                                                                                                          ,                                                                                                                        ⁢                                              (                        otherwise                        )                                                                                                        ⁢                                                          ⁢                              where:                            ⁢                                                           ⁢              k                        ,                                                            n                  ∈                                      {                                                                                   ⁢                                          …                      ⁢                                                                                           ,                                              -                        1                                            ,                      0                      ,                      1                      ,                      …                                        ⁢                                                                                   }                                                  ⁢                                                                   ⁢                                                                  ⁢                                  h                  ⁡                                      (                                          k                      ,                      n                                        )                                                              =                              impulse                ⁢                                                                   ⁢                response                ⁢                                                                   ⁢                of                ⁢                                                                   ⁢                the                ⁢                                                                   ⁢                filter                ⁢                                                                   ⁢                in                ⁢                                                                   ⁢                the                ⁢                                                                   ⁢                VT                                                                        (        1.1        )            The choice of h(k,n) depends upon whether it is a spatial, temporal or spatio-temporal filter.
Spatial linear interlace-to-progressive scan conversion uses the correlation between vertical neighboring pixels to interpolate the missing pixels. It has the characteristic of passing all temporal frequency responses, which guarantees the absence of motion artifacts. Defects occur with high vertical frequencies only. It is easy to implement and has the lowest hardware requirement since normally it only requires a few lines of buffer instead of one field buffer. It also doesn't require a complex computation to execute its filtering algorithm.
The simplest form of the spatial progressive scan conversion algorithm is line repetition. This algorithm doubles every line in the original fields. The frequency response of this interpolator is given by:Hy(fy)=|cos(πfy)|where:                fy is the vertical frequency (normalized to the vertical sampling frequency)        Hy(fy) is the frequency response in the vertical directionThis frequency characteristic has no steep roll off. As a consequence, the first spectral replica is not much suppressed, while the baseband is partly suppressed. This causes alias and blur in the output signal.        
Line Averaging is the most popular and commonly used Spatial filtering algorithm. It can be defined by equation (1.0) above, with h(k,0)=0.5 for k=±1 and h(k,n)=0 otherwise. The frequency response:                                           H            y                    ⁡                      (                          f              y                        )                          =                              1            2                    +                                    1              2                        ⁢                          cos              ⁡                              (                                  2                  ⁢                  π                  ⁢                                                                           ⁢                                      f                    y                                                  )                                                                        (        1.2        )            indicates a higher alias suppression. However, this suppresses the higher part of the baseband spectrum as well which causes the output signal to be blurred. In general, purely spatial filters cannot discriminate between baseband and repeat spectrum regardless of their length.
Temporal interlace-to-progressive scan conversion uses the correlation in the time domain. Pure temporal interpolation has the characteristic of passing all the spatial frequencies. Consequently, there is no degradation in stationary images.
The most popular temporal filtering algorithm is field insertion. The scan conversion is done by inserting the lines from the previous field to replace the missing lines. The formal definition is given by equation (1.0) with h(0,−1)=1 and h(k,n)=0 otherwise. The frequency characteristic is analogous to the line repetition given in equation (1.1), the only difference being that fy is replaced with ft.
Field insertion, also called “Weave” in PC world, provides an all-pass characteristic in the vertical frequency domain. It is the best solution in case of still images, as all vertical frequencies are preserved. However, moving objects are not shown at the same position for odd and even lines of a single output frame. This causes serration of moving edges, which is a very annoying artifact.
Longer temporal finite duration impulse response (FIR) filters require multiple field storage. Unlike signal processing for audio signals, this will increase the storage requirement significantly. Therefore it is economically unattractive. Furthermore, they still cannot discriminate between baseband and repeated spectra.
A spatio-temporal interpolation filter would theoretically solve the interlace-to-progressive scan conversion problem if the signal were band-limited prior to interlacing. The required pre-filter would be similar to the up-conversion filter. The required frequency characteristic is shown in FIG. 4.
Although the pre-filter is missing, and there are problems with motion tracking viewers, FIG. 4 illustrates that the spatial-temporal filter is certainly the best linear approach in that it prevents both alias and blur in stationary images. The vertical detail is gradually reduced with increasing temporal frequencies. Such a loss of resolution with motion is not unnatural.
The filter is usually designed such that the contribution from the neighboring fields is limited to the higher vertical frequencies. As a consequence, motion artifacts are absent for objects without vertical detail that move horizontally. Early versions of the Spatial-Temporal filtering reduces the filter into only two-dimensional (Vertical-Temporal) filter. The version that gives the best result, however, utilized other spatial neighboring pixels and can be defined as:                                           F            0                    ⁡                      (                          x              ,              y              ,              t                        )                          =                  {                                                                                                                                      ⁢                                              F                        ⁡                                                  (                                                      x                            ,                            y                            ,                            t                                                    )                                                                                                                                                (                                                                        y                          ⁢                                                                                                           ⁢                          mod                          ⁢                                                                                                           ⁢                          2                                                =                                                  t                          ⁢                                                                                                           ⁢                          mod                          ⁢                                                                                                           ⁢                          2                                                                    )                                                                                                                                                                                    ∑                          k                                                ⁢                                                                                                   ⁢                                                                              F                            ⁡                                                          (                                                              x                                ,                                                                  y                                  +                                  k                                                                ,                                                                  t                                  +                                  n                                                                                            )                                                                                ⁢                                                      h                            ⁡                                                          (                                                              k                                ,                                n                                                            )                                                                                                                          18                                                                                                                        ⁢                                              (                        otherwise                        )                                                                                                        ⁢                                                          ⁢                              h                ⁡                                  (                                      k                    ,                    n                                    )                                                      =                          {                                                                                                                ⁢                                              1                        ,                        8                        ,                        8                        ,                        1                                                                                                                                                (                                                                              k                            =                                                          -                              3                                                                                ,                                                      -                            1                                                    ,                          1                          ,                          3                                                )                                            ⋀                                              (                                                  n                          =                          0                                                )                                                                                                                                                                                -                        5                                            ,                      10                      ,                                              -                        5                                                                                                                                              ⁢                                                                        (                                                                                    k                              =                                                              -                                2                                                                                      ,                            0                            ,                            2                                                    )                                                ⋀                                                  (                                                      n                            =                                                          -                              1                                                                                )                                                                                                                                                                                                      ⁢                      0                                                                                                  (                      otherwise                      )                                                                                                                              (        1.3        )            
Linear Temporal interpolators are perfect in the absence of motion. Linear Spatial methods have no artifacts in case of no vertical detail occurs. It seems logical therefore, to adapt the interpolation strategy to motion and/or vertical detail. Many such systems have been proposed, mainly in the 1980's. The basic concept of these methods is that the methods have some kind of motion detection, which is implemented either implicitly or explicitly. The motion detector is used to decide whether the algorithm will do inter-field interpolation or intra-field interpolation. Inter-field interpolation is used in static situations while the intra-field interpolation is used with motion.
Non-linear algorithms consist primarily of implicitly adaptive, nonlinear algorithms and some explicitly adaptive nonlinear algorithms with motion detector (MD) algorithms. The implicitly adaptive, nonlinear algorithms provided the best affordable interlace-to-progressive scan conversion method for TV receivers until in the 1990's, when single-chip motion compensated methods become feasible. Implicitly adaptive, nonlinear algorithms are still widely used even now, especially in the computer community.
Median filtering is by far the most popular example of implicitly adaptive methods. The simplest version is a Three-Tap VT Median Filter. The interpolated samples are found as the median luminance value of the vertical neighbors and the temporal neighbor in the previous field. The formal definition of this filter is given by:                                           F            o                    ⁡                      (                          x              ,              y              ,              t                        )                          =                  {                                                                                        ⁢                                                            F                      ⁡                                              (                                                  x                          ,                          y                          ,                          t                                                )                                                              ,                                                                                                (                                                            y                      ⁢                                                                                           ⁢                      mod                      ⁢                                                                                           ⁢                      2                                        =                                          t                      ⁢                                                                                           ⁢                      mod                      ⁢                                                                                           ⁢                      2                                                        )                                                                                                      med                  (                                                            F                      ⁡                                              (                                                  x                          ,                                                      y                            -                            1                                                    ,                          t                                                )                                                              ,                                          F                      ⁡                                              (                                                  x                          ,                                                      y                            +                            1                                                    ,                          t                                                )                                                              ,                                          F                      ⁡                                              (                                                  x                          ,                          y                          ,                                                      t                            -                            1                                                                          )                                                              ,                                                                                                                  ⁢                                      (                    otherwise                    )                                                                                                          (        1.4        )            where med(A, B, C) is defined by:                               med          ⁡                      (                          A              ,              B              ,              C                        )                          =                  {                                                                      A                  ,                                                                                                  (                                          B                      <                      A                      <                      C                                        )                                    ⋁                                      (                                          C                      <                      A                      <                      B                                        )                                                                                                                        B                  ,                                                                                                  (                                          A                      ≤                      B                      ≤                      C                                        )                                    ⋁                                      (                                          C                      ≤                      B                      ≤                      A                                        )                                                                                                                        C                  ,                                                                                                ⁢                                      (                    otherwise                    )                                                                                                          (        1.5        )            (The formulae above can be generalized into any number of input values).
One of the attractive features of the median filter is its ability to preserve signal edges while suppressing impulse noise quite well. This is done by implicitly adapting to the motion or edges. The underlying assumption is that in case of stationarity, F(x, y, t) is likely to have a value between those of its vertical neighbors. Hence an inter-field (temporal) filtering is utilized. In case of motion, intra-field interpolation often results, since the correlation between the samples in the current field is likely to be the highest. Thus median filter automatically realizes intra/inter field switching on a pixel basis.
The median filter, however, exhibits some undesirable performance such as edge and plateau jitter for non-constant signal plus impulsive noise. Near the edge, the median filter allows bias error depending on the noise power and the height of signal edge. Applying smoothing prior to median filtering can limit this flaw.
The major drawback of median filtering is that it distorts vertical details and introduces alias. Hsu and Chen proposed a 2D Adaptive Separable Median Filter to reduce the alias (blocking) effect. This method is based on 1D adaptive median which can be defined as:             F      o        ⁡          (              x        ,        y        ,        t            )        =      {                                                    ⁢                                          F                ⁡                                  (                                      x                    ,                    y                    ,                    t                                    )                                            ,                                                            (                                          y                ⁢                                                                   ⁢                mod                ⁢                                                                   ⁢                2                            =                              t                ⁢                                                                   ⁢                mod                ⁢                                                                   ⁢                2                                      )                                                                                          ∑                                  i                  =                                      M                    -                    d                                                                    M                  +                  d                                            ⁢                                                           ⁢                                                                    x                    ^                                    i                                                  (                                                            2                      ⁢                      d                                        +                    1                                    )                                                      ,                                                            ⁢                          (              otherwise              )                                                              where:                                                                       M          =                                    (                              N                -                1                            )                        2                          ⁢                                  ⁢                  d          =                      {                                                                                                    ⁢                                          0                      ,                                                                                                            (                                          1                      >                      M                                        )                                                                                                                                          M                      -                      l                                        ,                                                                                        (                                          1                      ≤                      M                                        )                                                                                                          (        1.6        )                            l is the distance between the position of the filter and that of blocking effects.        
This algorithm was originally used for removing blocking effect in block-based image coding, but it can be easily adapted by giving l any specific value and combining this algorithm with a motion/edge detector. Despite all the disadvantages of the median filter, its superior properties at vertical edges and its low hardware cost have made it very successful.
Motion-adaptive methods use a motion detector algorithm to detect any movement inside the image. Based on the motion detector result, a filtering algorithm is used to convert the image from interlace to progressive. To detect the motion, the difference between two consecutive images is calculated. Normally this calculation is only done on the luminance data stream (the Y stream in the YUV format). Unfortunately, due to noise, the difference signal doesn't become zero in all parts of the picture that lack motion. Some systems have additional problems; for example, chrominance streams cause nonstationarities in color regions, interlace causes nonstationarities in vertical detail parts and timing jitter of the sampling clock is particularly harmful in horizontal detailed areas
To overcome these problems it is desirable that the motion detector output should have a multilevel signal output rather than just a simple binary. The multilevel signal can be used to give more information about the motion characteristic. Because of all these difficulties with motion detection, providing a practical motion detector is not trivial. Assumptions are necessary to realize a practical motion detector that yields an adequate performance in most cases. Common assumptions to improve the detector include:                1. Noise is small and signal is large        2. The spectrum part of the chrominance streams carries no motion information        3. The low frequency energy in signal is larger than in noise and alias        4. Objects are large compared to a pixel.A good motion detector must switch, or preferably fade, between two processing modes: one optimal for stationarity and the other for motion. An important aspect of designing a good motion-adaptive algorithm is determining the switching threshold or the fading function. Even with an adaptive switching/fading function, it is still difficult to make a function that can adapt to any kind of image.        
Those skilled in the art will appreciate that temporal and vertical filters may be combined to reject alias components and preserve frequency domain by applying motion adaptive fading. Fading between an interpolator optimized for static image parts and one for moving images parts can be achieved with the following function:                                           F            o                    ⁡                      (                          x              ,              y              ,              t                        )                          =                  {                                                                                        ⁢                                      F                    ⁡                                          (                                              x                        ,                        y                        ,                        t                                            )                                                                                                                    (                                                            y                      ⁢                                                                                           ⁢                      mod                      ⁢                                                                                           ⁢                      2                                        =                                          t                      ⁢                                                                                           ⁢                      mod                      ⁢                                                                                           ⁢                      2                                                        )                                                                                                                          α                    ⁢                                                                                   ⁢                                                                  f                        st                                            ⁡                                              (                                                  x                          ,                          y                          ,                          t                                                )                                                                              +                                                            (                                              1                        -                        α                                            )                                        ⁢                                                                  F                        mot                                            ⁡                                              (                                                  x                          ,                          y                          ,                          t                                                )                                                                                                                                                            ⁢                                      (                    otherwise                    )                                                                                                          (        1.7        )            With Fst the result of interpolation for static image parts and Fmot the result for moving image parts. The motion detector determines the mixed factor α.
It has been suggest by some that a well defined VT filter can perform as well as the best motion adaptive filter at a lower price. The idea is that in order to prevent switching artifacts the fading results in something very similar to VT filtering that needs no motion detector.
Others have suggested a fade between more than two interpolators. For example, in certain interpolators the high frequency information for the interpolated line is extracted from the previous line, while a motion adaptive interpolator determines the low frequency information.                                           F            o                    ⁡                      (                          x              ,              y              ,              t                        )                          =                  {                                                                      F                  ⁡                                      (                                          x                      ,                      y                      ,                      t                                        )                                                                                                (                                                            y                      ⁢                                                                                           ⁢                      mod                      ⁢                                                                                           ⁢                      2                                        =                                          t                      ⁢                                                                                           ⁢                      mod                      ⁢                                                                                           ⁢                      2                                                        )                                                                                                                                                                        F                                                  H                          ⁢                                                                                                           ⁢                          F                                                                    ⁡                                              (                                                  x                          ,                                                      y                            -                            1                                                    ,                          t                                                )                                                              +                                          α                      ⁢                                                                                           ⁢                                                                        F                          av                                                ⁡                                                  (                                                      x                            ,                            y                            ,                            t                                                    )                                                                                      +                                                                  (                                                  1                          -                          α                                                )                                            ⁢                                                                        F                          LF                                                ⁡                                                  (                                                      x                            ,                            y                            ,                                                          t                              -                              1                                                                                )                                                                                                      ,                                                                                                ⁢                                      (                    otherwise                    )                                                                                                          (        1.8        )            With FHF and FLF being the high pass and low pass filtered versions of input signal F. Fav is defined by:                               F          av                =                                                            F                                  L                  ⁢                                                                           ⁢                  F                                            ⁡                              (                                  x                  ,                                      y                    -                    1                                    ,                  t                                )                                      +                                          F                LF                            ⁡                              (                                  x                  ,                                      y                    +                    1                                    ,                  t                                )                                              2                                    (        1.9        )            With α controlled by the motion detector.
Another kind of motion detector is known as a “Mouse's Teeth Detector,” schematically illustrated in FIGS. 5 and 6. This motion detector uses a spatial offset in the vertical direction to detect the motion. The computational complexity of the algorithm is very low and requires memory for only one field instead of an entire frame. The output of the detector has 8 level that can be used to better define a motion between the fields.
Another strategy for motion detection involves edge detection. Certain edge dependent methods use a larger neighborhood of samples in order to capture information about the edge orientation. If an intra-field interpolation is necessary because of motion, then the interpolation should preferably preserve the baseband spectrum. After determining the least harmful filter orientation, the signal is interpolated in that direction. As shown in FIG. 7, the interpolated sample X is determined by a luminance gradient indication which is calculated from its immediate neighborhood. The formal definition is given by:                     X        =                  {                                                                                          X                    A                                    ,                                                                              (                                                            (                                              |                                                  A                          -                          F                                                |                                                  <                                                      |                                                          C                              -                              D                                                        |                                                                                              )                                        ⋀                                          (                                              |                                                  A                          -                          F                                                |                                                  <                                                      |                                                          B                              -                              E                                                        |                                                                                              )                                                        )                                                                                                                          X                    C                                    ,                                                                                                                                                                          (                                                      (                                                                                                                                                            C                                  -                                  D                                                                                                                            <                                                                                                                                A                                  -                                  F                                                                                                                                                      )                                                    )                                                ⋀                                                                                                        C                            -                            D                                                                                                                        <                                                                                                B                          -                          E                                                )                                                              )                                                                                                                                                              X                    B                                    ,                                                                              (                  otherwise                  )                                                                                        (        1.10        )                            where XA, XB, XC are defined by:             X      A        =                  A        +        F            2        ,            X      B        =                  B        +        E            2        ,            X      C        =                  C        +        D            2              and where the pixels A, B, C, D, E, and F are those indicated in FIG. 7, formally defined by:A=F(x−1,y−1,t)B=F(x,y−1,t)C=F(x+1,y−1,t)D=F(x−1,y+1,t)E=F(x+1,t)F=F(x+1,y+t,t)G=F(x,y−3,t)H=F(x,y+3,t)in a certain methods, XB is replaced by a VT median filter.        
It is uncertain whether a zero difference between pairs of neighboring samples indicates the spatial direction in which the signal is stationary. For example, noise—or more fundamentally, alias—can negatively influenced the decision. An edge detector can be applied to switch or fade between at least two processing modes, each of them optimal for interpolation for a certain orientation of the edge.
It is possible to increase the edge detection consistency by checking also the edge orientation at neighboring pixels. In certain methods, directional edge-detection operators are defined. For example, the error measurement for a vertical orientation is defined by:angle 90°=|B−E|+|C−F|  (1.11)and for an edge under 116 degrees:angle 116°=|A−E|+B−F|  (1.12)
Edge consistency information is further increased by looking for a dominating main direction in a near neighborhood. The problem of alias however, still remains.
Other methods of interpolation are hybrid methods, which mix linear and nonlinear methods. For example, in FIR Median hybrids, schematically illustrated in FIG. 8, first an 8-Tap VT filter is used. The output of the FIR filter is fed as one of the inputs of a five point median filter. The remaining four inputs are the nearest neighbors on the VT sampling grid.
Another kind of hybrid, the 9-Point Weighted Median, extends the aperture of median filter in the horizontal domain to enable implicit edge adaptation. It consist of 7 samples point, and the output of the median is defined by:                                           F            o                    ⁡                      (                          x              ,              y              ,              t                        )                          =                  med          ⁡                      (                          A              ,              B              ,              C              ,              D              ,              E              ,              F              ,                                                B                  +                  E                                2                            ,                              F                ⁡                                  (                                      x                    ,                    y                    ,                                          t                      -                      1                                                        )                                            ,                              F                ⁡                                  (                                      x                    ,                    y                    ,                                          t                      -                      1                                                        )                                                      )                                              (        1.13        )            where A, B, C, D, E, and F are the pixels as indicated in FIG. 7 and defined in equation 1.10.
Other methods extend this concept with a motion detector. For example, instead of using nine points, certain methods made the coefficient of ½(B+E) and F(x, y, t−1) adaptive. The motion detector controls the importance of the “weight” of these individual pixels at the input of the median filter. The output of the deinterlacer is defined by:                                           F            o                    ⁡                      (                          x              ,              y              ,              t                        )                          =                  {                                                                                          F                    ⁡                                          (                                              x                        ,                        y                        ,                        t                                            )                                                        ,                                                                              (                                                            y                      ⁢                                                                                           ⁢                                              mod                        ⁢                        2                                                              =                                          t                      ⁢                                                                                           ⁢                                              mod                        ⁢                        2                                                                              )                                                                                                      med                  (                                      A                    ,                    B                    ,                    C                    ,                    D                    ,                    E                    ,                    F                    ,                                          α                      ⁢                                                                                           ⁢                                              F                        ⁡                                                  (                                                      x                            ,                            y                            ,                                                          t                              -                              1                                                                                )                                                                                      ,                                          β                      ⁡                                              (                                                                              B                            +                            E                                                    2                                                )                                                              ,                                                                                                (                  otherwise                  )                                                                                        (        1.14        )            where α and β are the integer weights. αA indicates the number of A's that occur in equation 1.14. For example, 3A means A, A, A. A large value of α increases the probability of field insertion, whereas a large β increases the probability of line averaging at the output.
Another combination of implicit/explicit edge and motion adaptivity uses a hierarchical three-level motion detector that provides indications of static, slow, and fast motion. Based on this analysis, one of three different interpolators is selected. In the case of static images, a temporal FIR filter is selected. In the case of slow motion, the so-called weighed hybrid median filter (WHMF) is used. And in the case of fast motion, a spatial FIR filter is used as the interpolator. Applying the definitions of FIG. 7 yields:                               F          o                =                  {                                                                                          F                    ⁡                                          (                                              x                        ,                        y                        ,                        t                                            )                                                        ,                                                                              (                                                            y                      ⁢                                                                                           ⁢                                              mod                        ⁢                        2                                                              =                                          t                      ⁢                                                                                           ⁢                                              mod                        ⁢                        2                                                                              )                                                                                                                                                1                      2                                        ⁢                                          (                                                                        F                          ⁡                                                      (                                                          x                              ,                              y                              ,                                                              t                                -                                1                                                                                      )                                                                          +                                                  F                          ⁡                                                      (                                                          x                              ,                              y                              ,                                                              t                                +                                1                                                                                      )                                                                                              )                                                        ,                                                                              (                  static                  )                                                                                                                          med                    ⁡                                          (                                                                                                                                                                                                    α                                  0                                                                ⁢                                A                                                            +                                                              F                                2                                                                                                                                                                                                                                                                                          α                                  1                                                                ⁢                                B                                                            +                                                              E                                2                                                                                                                                                                                                                                                                                          α                                  2                                                                ⁢                                C                                                            +                                                              D                                2                                                                                                                                                                                                                                                        α                                3                                                            ⁡                                                              (                                                                                                      G                                    +                                    H                                                                    2                                                                )                                                                                                                                                        )                                                        ,                                                                              (                                      slow                    ⁢                                                                                   ⁢                    motion                                    )                                                                                                                                                                        c                        0                                            ⁢                      B                                        +                                                                  c                        1                                            ⁢                      E                                        +                                                                  c                        2                                            ⁢                      G                                        +                                                                  c                        3                                            ⁢                      H                                                        ,                                                                              (                                      fast                    ⁢                                                                                   ⁢                    motion                                    )                                                                                        (        1.15        )            The coefficients α1 are calculated according to Webers Law: “the eye is more sensitive to small luminance differences in dark area rather than in bright areas.”
Motion compensated methods are the most advanced interlace-to-progressive scan conversion algorithms available. Similarly to many of the algorithms discussed above, motion compensated methods try to interpolate in the direction with the highest correlation. With motion vectors available, this is an interpolation along the trajectory of motion. Using the motion compensation, a moving sequence can virtually be converted into a stationary one. Thus, methods that perform better for static image parts will profit from motion compensation.
It is very easy to add a motion compensation in any of the algorithms described above. However, in the following paragraphs, attention will be given to new algorithms that cannot be deduced directly from the non-motion compensated algorithms. The common feature of these methods is that they provide a solution to the fundamental problem of motion compensating sub-sampled data. This problem arises if the motion vector used to modify coordinates of pixels in a neighboring field does not point to a pixel on the interlaced sampling grid. In the horizontal domain, this causes no serious problem, with the application of sampling rate conversion theory. In the vertical domain, however, the demands for applying the sampling theorem are not satisfied, prohibiting correct interpolation.
A first approximation to cope with this fundamental problem is to perform a spatial interpolation whenever the motion vector points at a nonexisting sample, or even to round to the nearest pixel.
Certain more sophisticated methods depart from this approximation. Before actually performing an intra-field interpolation, the motion vector is extended into the previous fields to check whether this extended vector arrives in the vicinity of an existing pixel. The formal definition is given by:                                           F            o                    ⁡                      (                          x              ,              y              ,              t                        )                          =                  {                                                                                          F                    ⁡                                          (                                              x                        ,                        y                        ,                        t                                            )                                                        ,                                                                              (                                                            y                      ⁢                                                                                           ⁢                                              mod                        ⁢                        2                                                              =                                          t                      ⁢                                                                                           ⁢                                              mod                        ⁢                        2                                                                              )                                                                                                                          F                    ⁡                                          (                                                                        x                          -                                                                                    MV                              x                                                        ⁡                                                          (                                                              x                                ,                                y                                ,                                t                                                            )                                                                                                      ,                                                  y                          -                                                                                    MV                              y                                                        ⁡                                                          (                                                              x                                ,                                y                                ,                                t                                                            )                                                                                -                                                      ɛ                            y                                                                          ,                                                  t                          -                          1                                                                    )                                                        ,                                                                              (                                                                                    (                                                  y                          -                                                      MV                            y                                                    -                                                      ɛ                            y                                                                          )                                            ⁢                                              mod                        ⁢                        2                                                              =                                          t                      ⁢                                                                                           ⁢                                              mod                        ⁢                        2                                                                              )                                                                                                                          F                    ⁡                                          (                                              x                        ,                                                                              -                            2                                                    ⁢                                                                                    MV                              x                                                        ⁡                                                          (                                                              x                                ,                                y                                ,                                t                                                            )                                                                                                      ,                                                  y                          -                                                                                    MV                              y                                                        ⁡                                                          (                                                              x                                ,                                y                                ,                                t                                                            )                                                                                -                                                      2                            ⁢                                                          ɛ                              y                                                                                                      ,                                                  t                          -                          2                                                                    )                                                        ,                                                                              (                                                                                    (                                                  y                          -                                                      2                            ⁢                                                          MV                              y                                                                                -                                                      2                            ⁢                                                          ɛ                              y                                                                                                      )                                            ⁢                                              mod                        ⁢                        2                                                              =                                          t                      ⁢                                                                                           ⁢                                              mod                        ⁢                        2                                                                              )                                                                                                                          F                    ⁡                                          (                                                                        x                          -                                                                                    MV                              x                                                        ⁡                                                          (                                                              x                                ,                                y                                ,                                t                                                            )                                                                                                      ,                                                  y                          -                                                                                    MV                              y                                                        ⁡                                                          (                                                              x                                ,                                y                                ,                                t                                                            )                                                                                                      ,                                                  t                          -                          1                                                                    )                                                        ,                                                                              (                  otherwise                  )                                                                                        (        1.16        )            where εy is the small error resulting from rounding to the nearest grid position. εy has to be smaller than a threshold. If no motion compensated pixels appear in the vicinity of the required position it should be possible to find one even further backward in time. This is not recommended, however, as the motion vector loses validity by extending it too far.
The algorithm implicitly assumes uniform motion over a two-fields period, which is a drawback. Furthermore, the robustness to incorrect motion vectors is poor, since no protection is provided.
The Motion-compensated Time Recursive Algorithm came from the generalization of the fact that recursive filters have a lower implementation complexity than FIR filters. Even first-order linear recursive filters have infinite impulse response and produce output depending on the whole history of input. The Motion-compensated Time Recursive Algorithm uses a previously deinterlaced frame instead of the previous field. Once a perfectly deinterlaced image is available, and the motion vectors are accurate, sampling rate conversion theory can be used to interpolate the samples required to deinterlace the current field. The formal definition is given by:                                           F            o                    ⁡                      (                          x              ,              y              ,              t                        )                          =                  {                                                                                          F                    ⁡                                          (                                              x                        ,                        y                        ,                        t                                            )                                                        ,                                                                              (                                                            y                      ⁢                                                                                           ⁢                                              mod                        ⁢                        2                                                              =                                          n                      ⁢                      mod                      ⁢                      2                                                        )                                                                                                                                                F                      o                                        ⁡                                          (                                              x                        ,                                                  -                                                                                    MV                              x                                                        ⁡                                                          (                                                              x                                ,                                y                                ,                                t                                                            )                                                                                                      ,                                                  y                          -                                                                                    MV                              y                                                        ⁡                                                          (                                                              x                                ,                                y                                ,                                t                                                            )                                                                                                      ,                                                  t                          -                          1                                                                    )                                                        ,                                                                              (                  otherwise                  )                                                                                        (        1.17        )            The initial condition Fo(x, y, 0) is equal to F(x, y, 0) where F(x, y, t) is the output of a linear spatial interpolation.
As can be seen in FIG. 9, the interpolated samples generally depend on previous original samples as well as previously interpolated samples. Thus errors originating from one output frame can propagate into subsequent output frames. This is inherent to the recursive approach and is the worst drawback of this approach.
To prevent serious errors from propagating, the following algorithm has been proposed:                                           F            o                    ⁡                      (                          x              ,              y              ,              t                        )                          =                  {                                                                                          F                    ⁡                                          (                                              x                        ,                        y                        ,                        t                                            )                                                        ,                                                                              (                                                            y                      ⁢                                                                                           ⁢                                              mod                        ⁢                        2                                                              =                                          n                      ⁢                      mod                      ⁢                      2                                                        )                                                                                                                                                (                                              1                        -                        c                                            )                                        ⁢                                                                  F                        ^                                            ⁡                                              (                                                  x                          ,                          y                          ,                          t                                                )                                                                              +                                                                                                                                                                                                         c                    ⁢                                                                                   ⁢                                                                  F                        o                                            ⁡                                              (                                                  x                          ,                                                      -                                                                                          MV                                x                                                            ⁡                                                              (                                                                  x                                  ,                                  y                                  ,                                  t                                                                )                                                                                                              ,                                                      y                            -                                                                                          MV                                y                                                            ⁡                                                              (                                                                  x                                  ,                                  y                                  ,                                  t                                                                )                                                                                                              ,                                                      t                            -                            1                                                                          )                                                                              ,                                                                              (                  otherwise                  )                                                                                        (        1.18        )            
Aliasing at the output of the deinterlaced results in nonstationarity along the motion trajectory. Such nonstationarities can be suppressed using a filter. Cost effective filtering in the spatial, temporal, or spatio-temporal domain can best be realized with a recursive filter.
Certain methods extended the idea of the time recursive algorithm and proposed a motion-compensated first-order recursive temporal filter given by:                                           F            o                    ⁡                      (                          x              ,              y              ,              t                        )                          =                  {                                                                                                                k                      ⁢                                                                                           ⁢                                              F                        ⁡                                                  (                                                      x                            ,                            y                            ,                            t                                                    )                                                                                      +                                                                  (                                                  1                          -                          k                                                )                                            ⁢                                                                        F                          o                                                ⁡                                                  (                                                                                    x                              -                                                              M                                ⁢                                                                                                                                   ⁢                                                                                                      V                                    x                                                                    ⁡                                                                      (                                                                          x                                      ,                                      y                                      ,                                      t                                                                        )                                                                                                                                                        ,                                                          y                              -                                                                                                MV                                  y                                                                ⁡                                                                  (                                                                      x                                    ,                                    y                                    ,                                    t                                                                    )                                                                                                                      ,                                                          t                              -                              1                                                                                )                                                                                                      ,                                                                              (                                                            y                      ⁢                                                                                           ⁢                                              mod                        ⁢                        2                                                              =                                          t                      ⁢                                                                                           ⁢                                              mod                        ⁢                        2                                                                              )                                                                                                                                                p                      ⁢                                                                                           ⁢                                                                        F                          i                                                ⁡                                                  (                                                      x                            ,                            y                            ,                            t                                                    )                                                                                      +                                                                  (                                                  1                          -                          p                                                )                                            ⁢                                                                        F                          o                                                ⁡                                                  (                                                      x                            ,                                                                                          -                                M                                                            ⁢                                                                                                                           ⁢                                                                                                V                                  x                                                                ⁡                                                                  (                                                                      x                                    ,                                    y                                    ,                                    t                                                                    )                                                                                                                      ,                                                          y                              -                                                                                                MV                                  y                                                                ⁡                                                                  (                                                                      x                                    ,                                    y                                    ,                                    t                                                                    )                                                                                                                      ,                                                          t                              -                              1                                                                                )                                                                                                      ,                                                                              (                  otherwise                  )                                                                                        (        1.19        )            where p and k are adaptive parameters and Fl, is the output of any initial interlace-to-progressive Conversion algorithm. Preferably a simple method is used, such as line averaging. The derivation of k is fairly straightforward and is comparable to what we see in edge preserving recursive filters, which are used for motion-adaptive noise reduction.
A similar derivation for p is not obvious, since the difference would heavily depend upon the quality of the initial deinterlacer. To solve this problem, the factor p is selected such that the nonstationarity along the motion trajectory of the resulting output for interpolated pixels equals that of the vertically neighboring original pixels. This assumption leads to:                                           p            ⁡                          (                              x                ,                y                ,                t                            )                                =                                    |                              A                +                B                            |                              +                δ                                                    2              |                                                                    F                    i                                    ⁡                                      (                                          x                      ,                      y                      ,                      t                                        )                                                  -                                                      F                    o                                    ⁡                                      (                                          x                      ,                                                                        -                          M                                                ⁢                                                                                                   ⁢                                                                              V                            x                                                    ⁡                                                      (                                                          x                              ,                              y                              ,                              t                                                        )                                                                                              ,                                              y                        -                                                  M                          ⁢                                                                                                           ⁢                                                                                    V                              y                                                        ⁡                                                          (                                                              x                                ,                                y                                ,                                t                                                            )                                                                                                                          ,                                              t                        -                        1                                                              )                                                              |                              +                δ                                                    ⁢                                  ⁢                              where            :                                                  ⁢            A                    =                                                    F                o                            ⁡                              (                                  x                  ,                                      y                    -                    1                                    ,                  t                                )                                      -                                          F                o                            ⁡                              (                                                      x                    -                                                                  MV                        x                                            ⁡                                              (                                                  x                          ,                          y                          ,                          t                                                )                                                                              ,                                      y                    -                                                                  MV                        y                                            ⁡                                              (                                                  x                          ,                          y                          ,                          t                                                )                                                              -                    1                                    ,                                      t                    -                    1                                                  )                                                    ⁢                                  ⁢                  B          =                                                    F                o                            ⁡                              (                                  x                  ,                                      y                    +                    1                                    ,                  t                                )                                      -                                          F                o                            ⁡                              (                                  x                  ,                                      -                                                                  MV                        x                                            ⁡                                              (                                                  x                          ,                          y                          ,                          t                                                )                                                                              ,                                      y                    -                                                                  MV                        y                                            ⁡                                              (                                                  x                          ,                          y                          ,                          t                                                )                                                              +                    1                                    ,                                      t                    -                    1                                                  )                                                                        (        1.19        )                            and where δ is a small constant, to prevent division by zero.        
The recursion is an essential ingredient of the concept. Consequently, the adaptive-recursive approach, similar to the time-recursive approach, has the risk of error propagation as its main disadvantage.
As can be seen from the discussion above, motion estimation is used to improve the accuracy of the prediction of lines in interlaced-to progressive scan conversion. (Motion estimation also has various applications in the image, video processing, and computer vision or robotics area.) Linear or temporal interpolators are perfect in the absence of motion, but in the presence of motion, especially multiple motions in one frame, motion estimation is essential in order to have a good prediction of the missing lines.
In general, motion estimation can be divided into three categories: (1) Pixel-by-pixel motion estimation (sometimes called “pel-recursive algorithms,” or “PRAs”); (2) Block-by-block motion estimation (commonly called “block matching algorithms,” or “BMAs”; and (3) advanced motion estimation methods.
Pel-recursive algorithms have rarely been used because they are inherently complex and quite difficult to implement. Another problem with PRAs is that the motion estimation algorithms sometimes run into convergence problems.
One well-known PRA is gradient matching. FIG. 10 illustrates the principle of gradient matching. At a given point in a picture, the function of brightness with respect to distance across the screen will have a certain slope, known as the spatial luminance gradient. If the associated picture area is moving, the slope will traverse a fixed point on the screen and the result will be that the brightness now changes with respect to time. For a given spatial gradient, the temporal gradient becomes steeper as the speed of movement increases. Thus motion speed can be estimated from the ratio of the spatial and temporal gradients.
In practice this is difficult because there are numerous processes which can change the luminance gradient. When an object moves so as to obscure or reveal the background, the spatial gradient will change from field to field even if the motion is constant. Various illuminations, such as when an object moves into shade, also cause difficulty. The process can be assisted by recursion, in which the motion is estimated over a larger number of fields, but this will result in problems directly after a scene change.
Phase correlation is another kind of PRA. A block diagram of a basic phase correlator is provided in FIG. 11. A phase correlator works by performing a discrete Fourier transform on two successive fields and then subtracting all of the phases of the spectral components. The phase differences are then subject to a reverse transform which directly reveals peaks whose positions correspond to motions between the fields. The nature of the transform domain means that if the distance and the direction of the motion are measured accurately, the area of the screen in which they took place is not. Thus in practical systems the phase correlation stage is followed by a matching stage not dissimilar to the block matching process. However, the matching process is steered by the motions from the phase correlation, and so there is no need to attempt to match at all possible motions. The similarities between the two from the practical perspective causes some people think of phase correlation as another branch of block matching.
One way of considering phase correlation is to think of the Fourier transform as breaking the picture into its constituent spatial frequencies. The hierarchical structure of block matching at various resolutions is in fact performed in parallel. In this way small objects are not missed because they will generate high-frequency components in the transform.
Although the matching process is simplified by adopting phase correlation, the Fourier transforms themselves require complex calculations. The high performance of phase correlation would remain academic because it's too difficult to implement, were it not for an important assumption about the range of motion speeds. When realistic values are used for the motion speed the computation required by block matching actually exceeds that required for phase correlation. FIG. 12 provides a block diagram of a practical phase correlated motion estimator.
The elimination of amplitude information from the phase correlation process ensures that motion estimation continues to work in the case of fades, objects moving into shade, or flashgun firings.
Block matching is the simplest approach to motion compensation. Even though it is not optimal, it has been widely used, and is the preferred technique in inter-frame motion compensated (MC) hybrid coding, interlace-to-progressive scan conversion, and other video/image processing related areas. The reason for this is the ease of implementation, because it doesn't require complicated circuitry. The idea of block matching, as illustrated in FIG. 13, is to calculate motion of a block of pixels by comparing it within a frame or field. Normally the search is constrained to searching within a specific window.
In block matching motion estimation algorithms a displacement/motion vector (MV) is assigned to the center of a block pixel B(x, y, t) in the current field t. If you assume that the block is M×N pixel size, B(x, y, t) can be described as:B(x,y,t)=└{(x,y)|Xx−N/2≦x≦Xx+N/2Xy−M/2≦y≦Xy+M/2},t┘  (1.20)Where X=(Xx,Xy)T is the center of B(x, y, t).
The motion vector MV (x,y,t) is determined by comparing the present field block with the previous field. The goal is to find the best match or least distorted block from the previous field. The best matched block has a center, which is shifted with respect to X over the motion MV (x,y,t).
It's desirable to compare all the possible positions to get the optimal MV. However this is impractical and it requires a lot of overhead processing. In order to make it practical to implement, the search is constrained within a specific window, which is centered at X.
The window can be specified as:                               W          ⁡                      (                          x              ,              y              ,                              t                -                1                                      )                          =                  [                                    {                                                                    (                                          x                      ,                      y                                        )                                    ||                  x                                |                                  ≤                                                            N                      2                                        +                                          n1                      ⋀                                                                      |                y                |                                  ≤                                                            M                      2                                        +                    m2                                                              }                        ,                          t              -              1                                ]                                    (        1.21            
The window is illustrated in FIG. 14 [2.15].
In most cases it's nearly impossible to get a similar block from the previous field. The motion vector MV (x,y,t) resulting from the block-matching process is a candidate vector C which yields the minimum value of an error function e(C, X, t). S is defined as the set of all possible C within MV (x,y,t−1).                               S          =                      {                                                            C                  _                                ||                                  C                  x                                            |                              ≤                                  n1                  ⋀                                            |                              C                y                            |                              ≤                m2                                      }                          ⁢                                  ⁢                                                            M                ⁢                                                                   ⁢                V                            _                        ⁢                          (                              x                ,                y                ,                t                            )                                ∈                      {                                                            C                  _                                ∈                S                            |                                                e                  ⁡                                      (                                                                  C                        _                                            ,                                              X                        _                                            ,                      t                                        )                                                  ≤                                                      e                    ⁡                                          (                                                                        F                          _                                                ,                                                  X                          _                                                ,                        t                                            )                                                        ⁢                                      ∀                                                                  F                        _                                            ∈                      S                                                                                            }                                              (        1.22        )            
Assuming that all the pixels in B(x, y, t) have the same motion, then MV (x,y,t) with the smallest matching error is assigned to all pixel positions of B(x, y, t):∀(x,y)εB(x,y,t): {overscore (MV)}(x,y,t)ε{{overscore (C)}εS|e({overscore (C)},{overscore (X)},t)≦e({overscore (F)},{overscore (X)},t)∀{overscore (F)}εS}  (1.23)
The error value for a given candidate vector C is a function of the luminance values of the pixels in the current block B(x,y,t) and those of the shifted block from the previous field, summed over the block B(x,y,t). Methods to calculate e(C, X, t) include:
Mean absolute Error (MAE) or Sum of the absolute Differences (SAD):                                                         M              1                        ⁡                          (                              i                ,                j                            )                                =                                                    1                                  M                  ⁢                                                                           ⁢                  N                                            ⁢                                                ∑                                      p                    =                    1                                    N                                ⁢                                  ∑                                      q                    =                    1                                    M                                                      |                                          (                                                      X                                          p                      ,                      q                                                        ,                  n                                )                            -                              (                                                      X                                                                  p                        +                        i                                            ,                                              q                        +                        j                                                                              ,                                      n                    -                    1                                                  )                                      |                          ,                                  ⁢                  |          i          |                      ≤            n1                          ,                  |          j          |                      ≤            m2                                              (        1.24        )            
Mean Square Error (MSE):                                                         M              2                        ⁡                          (                              i                ,                j                            )                                =                                    1                              M                ⁢                                                                   ⁢                N                                      ⁢                                          ∑                                  p                  =                  1                                N                            ⁢                                                ∑                                      q                    =                    1                                    M                                ⁢                                                      (                                                                  (                                                                              X                                                          p                              ,                              q                                                                                ,                          n                                                )                                            -                                              (                                                                              X                                                                                          p                                +                                i                                                            ,                                                              q                                +                                j                                                                                                              ,                                                      n                            -                            1                                                                          )                                                              )                                    2                                                                    ,                                  ⁢                  |          i          |                      ≤            n1                          ,                  |          j          |                      ≤            m2                                              (        1.25        )            
Cross-correlation Function:                                                         M              3                        ⁡                          (                              i                ,                j                            )                                =                                                    ∑                                  p                  =                  1                                N                            ⁢                                                ∑                                      q                    =                    1                                    M                                ⁢                                                      (                                                                  X                                                  p                          ,                          q                                                                    ,                      n                                        )                                    ⁢                                      (                                                                  X                                                                              p                            +                            i                                                    ,                                                      q                            +                            j                                                                                              ,                                              n                        -                        1                                                              )                                                                                                                                            [                                                                  ∑                                                  p                          =                          1                                                N                                            ⁢                                                                        ∑                                                      q                            =                            1                                                    M                                                ⁢                                                                              (                                                                                          X                                                                  p                                  ,                                  q                                                                                            ,                              n                                                        )                                                    2                                                                                      ]                                                        1                    /                    2                                                  ⁡                                  [                                                            ∑                                              p                        =                        1                                            N                                        ⁢                                                                  ∑                                                  q                          =                          1                                                M                                            ⁢                                                                        (                                                                                    X                                                                                                p                                  +                                  i                                                                ,                                                                  q                                  +                                  j                                                                                                                      ,                                                          n                              -                              1                                                                                )                                                2                                                                              ]                                                            1                /                2                                                    ,                                  ⁢                  |          i          |                      ≤            n1                          ,                  |          j          |                      ≤            m2                                              (        1.26        )            Mean Absolute Error is presently the most commonly implemented method on ICs, since it permits the simplest circuitry. In several simulations Mean Absolute Error performs as well as Mean Square Error. The Cross-correlation is the best method in the sense that it produce less error, but it requires a lot of computation, which makes it impractical to implement.
Block Matching Algorithm techniques depend upon several assumptions:                (1). No rotational motion occurs inside the block        (2) Objects have inertia        (3) The window is sufficiently large to capture the motion from frame to frame        
The consequence of assumptions 1 and 2 is that the MV (xy,t) that assign to X is applied to all the pixels in the blocks. Also B(x,y,t) should be small enough so that in cases where there is a rotational motion of an object in a frame, it can be translate into straight vector MV (x,y,t) at the block level.
Another thing that should be considered is the window size. If the window is not big enough, there is a chance that the MV (x,y,t) that we get is not optimal, especially in the case of a very fast moving objects.
Conceptually, the simplest approach to block matching is brute-force, or full search block matching. This approach involves searching every possible position. This gives the global optima, but at the expense of extensive computation. The magnitude of the computational load is exacerbated by the need to extend motion estimation to sub-pixel accuracy. As shown in FIG. 15 the increase in potential match loci for even half-pixel accuracy involves a quadrupling of the number of possible solutions that must be searched. A motion vector resolution of ¼ pixel accuracy is normally considered as a near true-motion vector field.
Though brute search BMAs give a global optima result, it requires more complex circuitry or more time to process. Most of the motion estimation ICs right now implement a full search algorithm. The complex circuitry makes the price of these ICs impractical for most applications. It's desirable to have an affordable consumer IC for motion estimation. In some applications, a local optima solution is sufficient. This has led to development of more efficient motion estimation approaches, which test only a subset of candidate vectors.
One of these approaches is conjugate direction searching (CDS). One-at-a-time searching (OTS) is a simplified version of conjugate direction search. OTS tracks the motion alternately horizontally and vertically, as shown in FIG. 16. A modified and improved version of this approach, one-dimensional full search motion estimation, has recently been developed.
Another block searching strategy is logarithmic searching. Logarithmic searching was the first simplified search strategy published. The logarithmic search tracks block motion along the direction of minimum distortion, as illustrated in FIG. 17.
Yet another block searching strategy is three-step searching, illustrated in FIG. 18. This is a fine-coarse search mechanism. At each step, the algorithm calculates and compares 9 points. Assuming that the center for the first step is X=(Xx,Xy)T, the algorithm for each step can be described as:({overscore (X)}′,t)={{overscore (C)}εS|e({overscore (C)},t)≦e({overscore (F)},t)∀{overscore (F)}εS}  (1.27)                where        ({overscore (X)}′,t) is the new center point        {overscore (C)}: candidate point                    ε{{overscore (X)}+aŪt,}                              U          _                i            =                           ⁢              {                              (                                                            0                                                                              0                                                      )                    ,                                           ⁢                      (                                                            0                                                                              1                                                      )                    ,                                           ⁢                      (                                                            1                                                                              1                                                      )                    ,                                           ⁢                      (                                                            1                                                                              0                                                      )                    ,                                           ⁢                      (                                                            1                                                                                                  -                    1                                                                        )                    ,                                           ⁢                      (                                                            0                                                                                                  -                    1                                                                        )                    ,                                           ⁢                      (                                                                                -                    1                                                                                                                    -                    1                                                                        )                    ,                                           ⁢                      (                                                                                -                    1                                                                                                0                                                      )                    ,                                           ⁢                      (                                                                                -                    1                                                                                                1                                                      )                          }              ⁢                       a    =          {                                                  4              ;                                                          for              ⁢                                                           ⁢              step              ⁢                                                           ⁢              I                                                                          2              ;                                                          for              ⁢                                                           ⁢              step              ⁢                                                           ⁢              I              ⁢                                                           ⁢              I                                                                          1              ;                                                          for              ⁢                                                           ⁢              step              ⁢                                                           ⁢              I              ⁢                                                           ⁢              I              ⁢                                                           ⁢              I                                                      e(C,t) and e(F,t) is error from the corresponding points.And the motion vector:{overscore (MV)}(x,y,t)=({overscore (X)}′″,t)−({overscore (X)},t)  (1.27){overscore (X)}′″ is the center point after the 3rd step.                        
Still another strategy for block searching is hierarchical searching. A block diagram of a hierarchical searching algorithm is illustrated in FIG. 19. This process involves decimating (sub-sampling) the present image and the reference image successively both horizontally and vertically. The search process starts with the lowest resolution images, using a small block size. The motion vector estimated at the first stage is used as the starting points for motion estimation at the next stage. Note that block size is now doubled along both directions. This process is repeated until the original resolution images are reach. The HDTV codec propose by Zenith and AT&T uses hierarchical searching for motion estimation
Another block search strategy is 3D recursive search motion estimation. The concept of this method is to store all the information of the motion vectors (MV) from the previous field and use that as a comparison to predict the new motion vector from the current field. At the top of the field, the prediction only involves the temporal neighboring motion vector. After the top motion vectors of the current field have been found, the prediction involves both the spatial and temporal neighboring motion vectors.
This algorithm tries to overcome the problem of one-dimensional recursive searching and tries to focus on the smoothness of the motion vectors. In one-dimensional recursive searching, like one-at-a-time searching, the resulting smoothness of these algorithms is insufficient. This is assumed to be caused by a large number of evaluated candidate vectors located around the spatial or temporal prediction value. This can cause strong deviation from the prediction, like inconsistencies in the velocity field, as the vector selection criterion applied in block matching (minimum match error) cannot guarantee returning true motion vectors. The fundamental difficulty with a one-dimensionally recursive algorithm is that it cannot cope with discontinuities in the velocity plane.
Certain 3D recursive search algorithms make the assumption that the discontinuities in the velocity plane are spaced at a distance that enables convergence of the recursive block matcher between two discontinuities. The recursive block matcher yields the correct vector value at the first side of the object boundary and starts converging at the opposite side. The convergence direction here points from side one to side two. Either side of the contour can be estimated correctly, depending on the convergence direction chosen, though not both simultaneously. Based on this, two estimators are applied concurrently, as indicated in FIG. 20, with opposite convergence directions. A mean absolute error criterion is used to decide which of these two estimators yields the correct displacement vector at the output.
This bidirectional convergence is hereinafter referred to as 2-D Convergence. The process is formally defined by:                                           ∀                                          (                                  x                  ,                  y                                )                            ∈                              B                ⁡                                  (                                      x                    ,                    y                    ,                    t                                    )                                                              :                                                    M                ⁢                                                                   ⁢                V                            _                        ⁢                          (                              x                ,                y                ,                t                            )                                      =                  {                                                                                                                                                                                                                            M                              ⁢                                                                                                                           ⁢                              V                                                        _                                                    a                                                ⁢                                                  (                                                      x                            ,                            y                            ,                            t                                                    )                                                                    ,                                                                                                  (                                                                        e                          ⁡                                                      (                                                                                                                                                                M                                    ⁢                                                                                                                                                   ⁢                                    V                                                                    _                                                                a                                                            ,                                                              X                                _                                                            ,                              t                                                        )                                                                          ≤                                                  e                          ⁡                                                      (                                                                                                                                                                M                                    ⁢                                                                                                                                                   ⁢                                    V                                                                    _                                                                b                                                            ,                                                              X                                _                                                            ,                              t                                                        )                                                                                              )                                                                                                                                                                                                                                              M                              ⁢                                                                                                                           ⁢                              V                                                        _                                                    b                                                ⁢                                                  (                                                      x                            ,                            y                            ,                            t                                                    )                                                                    ,                                                                                                  (                                                                        e                          ⁡                                                      (                                                                                                                                                                M                                    ⁢                                                                                                                                                   ⁢                                    V                                                                    _                                                                a                                                            ,                                                              X                                _                                                            ,                              t                                                        )                                                                          ≥                                                  e                          ⁡                                                      (                                                                                                                                                                M                                    ⁢                                                                                                                                                   ⁢                                    V                                                                    _                                                                b                                                            ,                                                              X                                _                                                            ,                              t                                                        )                                                                                              )                                                                                  ⁢                                                          ⁢                              where                :                                                                  ⁢                                  e                  ⁡                                      (                                                                                                                        M                            ⁢                                                                                                                   ⁢                            V                                                    _                                                a                                            ,                                              X                        _                                            ,                      t                                        )                                                                        =                                                            ∑                                      x                    ∈                                          B                      ⁡                                              (                                                  x                          ,                          y                          ,                          t                                                )                                                                                            ⁢                                  |                                                            F                      ⁡                                              (                                                  x                          ,                          y                          ,                          t                                                )                                                              -                                          F                      ⁡                                              (                                                                              x                            -                                                          M                              ⁢                                                                                                                           ⁢                                                              V                                                                  a                                  ⁢                                                                                                                                           ⁢                                  x                                                                                                                                              ,                                                      y                            -                                                          M                              ⁢                                                                                                                           ⁢                                                              V                                                                  a                                  ⁢                                                                                                                                           ⁢                                  y                                                                                                                                              ,                                                      t                            -                            T                                                                          )                                                                              |                                                                          ⁢                                      e                    ⁡                                          (                                                                                                                                  M                              ⁢                                                                                                                           ⁢                              V                                                        _                                                    b                                                ,                                                  X                          _                                                ,                        t                                            )                                                                                  =                                                ∑                                      x                    ∈                                          B                      ⁡                                              (                                                  x                          ,                          y                          ,                          t                                                )                                                                                            ⁢                                  |                                                            F                      ⁡                                              (                                                  x                          ,                          y                          ,                          t                                                )                                                              -                                          F                      ⁡                                              (                                                                              x                            -                                                          M                              ⁢                                                                                                                           ⁢                                                              V                                                                  b                                  ⁢                                                                                                                                           ⁢                                  x                                                                                                                                              ,                                                      y                            -                                                          M                              ⁢                                                                                                                           ⁢                                                              V                                                                  b                                  ⁢                                                                                                                                           ⁢                                  y                                                                                                                                              ,                                                      t                            -                            T                                                                          )                                                                              |                                                                                        (        1.28        )            
MVa and MVb are found in a spatial recursive process and can be calculated using equations 1.22 and 1.23. The updating prediction vectors Sa (x, y, t) are given by:                                                         S              _                        a                    ⁡                      (                          x              ,              y              ,              t                        )                          =                                            MV              _                        a                    ⁡                      (                                                            X                  _                                -                                                      SMV                    _                                    a                                            ,              t                        )                                              (        1.29        )                                                                    X              _                        b                    ⁡                      (                          x              ,              y              ,              t                        )                          =                                            MV              _                        b                    ⁡                      (                                                            X                  _                                -                                                      SMV                    _                                    b                                            ,              t                        )                                              (        1.30        )                                where        ⁢                  :                                                                                           SMV            _                    a                ≠                              SMV            _                    b                                    (        1.31        )            and where SMV points from the center of the block from which the prediction vector is taken to the center of the current block.
As indicated in condition 1.31, the two estimators have unequal spatial recursion vectors. If the two convergence directions are opposite (or at least different), the 2-D Convergence solves the run-in problem at the boundaries of moving objects. This is because one of the estimators will have converged already at the position where the other is yet to do so. Hence the concept combines the consistent velocity field of a recursive process with the fast step response as required at the contours of moving objects. The attractiveness of a convergence direction varies significantly for hardware. Referring to FIG. 21, the predictions taken from blocks 1, 2, or 3 are convenient for hardware and blocks 6, 7, 8 are totally unattractive.
The 3D Recursive approach extends the concept of the 2-D Convergence by adding convergence accelerators (CA), which are taken from the temporal neighboring prediction vectors. The spatial predictions are selected to yield two perpendicular diagonal convergence axes, as given by the following equations, and illustrated in FIG. 22.                                                                         S                _                            a                        ⁡                          (                              x                ,                y                ,                t                            )                                =                                                                      M                  ⁢                                                                           ⁢                  V                                _                            a                        ⁢                          (                                                                    X                    _                                    -                                      (                                                                                            X                                                                                                                      Y                                                                                      )                                                  ,                t                            )                                      ⁢                                  ⁢                                                            S                _                            b                        ⁡                          (                              x                ,                y                ,                t                            )                                =                                                                      M                  ⁢                                                                           ⁢                  V                                _                            b                        ⁢                          (                                                                    X                    _                                    -                                      (                                                                                                                        -                            X                                                                                                                                                Y                                                                                      )                                                  ,                t                            )                                                          (        1.32        )            
The Convergence Accelerator (CA) is another estimator that is selected along the convergence direction of each original estimator. To cope with the casuality, instead of introducing new estimators c and d, it uses a temporal neighboring motion vector from the previous field (Ta, and and Tb for estimators a and b respectively). The concept is that the new candidate in each original estimator accelerates the convergence of the individual estimator by introducing a look ahead into the convergence direction. These convergence accelerators are not taken from the corresponding block in the previous field, but from a block shifted diagonally over r blocks and opposite to the blocks which the spatial predictions S7a and S7b.{overscore (T)}a(x,y,t)={overscore (MV)}(x+r·X,y+r·Y,t−T){overscore (T)}b(x,y,t)={overscore (MV)}(x+r·−X,y+r·Y,t−T)  (1.33)
Increasing r implies a larger look ahead, but the reliability of the prediction decreases correspondingly, as the correlation between the vectors in a velocity plane can be expected to drop with increasing distance. r=2 has been experimentally found to the best for a block size of 8*8 pixels. The resulting relative positions are drawn in FIG. 23.
For the resulting 3D RS block matching algorithm, the motion vector MV(x, y, t) is calculated according to equation 1.28, where MVa(x,y,t) and MVb(x,y,t) result from estimators a and b respectively, and are taken from a candidate set CS. The motion vector range is limited to CSmax (which is the search window defined in 1.28) and the proposed candidate set CSa (x,y,t) for estimator a applying this updating strategy, hereinafter referred to as asynchronous cyclic search (ACS), defined as:                               C          ⁢                                           ⁢                                    S              a                        ⁡                          (                              x                ,                y                ,                t                            )                                      =                                                                              {                                                                                                              C                          _                                                ∈                                                  C                          ⁢                                                                                                           ⁢                                                      S                            max                                                                                              |                                              C                        _                                                              =                                                                                                                                                      M                              ⁢                                                                                                                           ⁢                              V                                                        _                                                    a                                                ⁢                                                  (                                                                                    x                              -                              X                                                        ,                                                          y                              -                              Y                                                        ,                            t                                                    )                                                                    +                                                                                                    U                            _                                                    a                                                ⁡                                                  (                                                      x                            ,                            y                            ,                            t                                                    )                                                                                                      }                                ⋃                                                                                        {                                                                            M                      ⁢                                                                                           ⁢                      V                                        _                                    ⁢                                      (                                                                  x                        +                                                  2                          ⁢                          X                                                                    ,                                              y                        +                                                  2                          ⁢                          Y                                                                    ,                                              t                        -                        T                                                              )                                    ⁢                  .0                                }                                                                        (        1.34        )            
where:Ūa(x,y,t)ε{0,lut(Nbl(x,y,t)mod p)}                where Nbl is the output of a block counter, lut is a look up table function, and p is a number which not a factor of the number of blocks in the picture (preferably a prime number).The candidate set for b is given by                                           C            ⁢                                                   ⁢                                          S                b                            ⁡                              (                                  x                  ,                  y                  ,                  t                                )                                              =                                    {                                                                                          C                      _                                        ∈                                          C                      ⁢                                                                                           ⁢                                              S                                                                                                                                   ⁢                          max                                                                                                      |                                      C                    _                                                  =                                                                                                                              M                          ⁢                                                                                                           ⁢                          V                                                _                                            b                                        ⁢                                          (                                                                        x                          -                          X                                                ,                                                  y                          +                          Y                                                ,                        t                                            )                                                        +                                                                                    U                        _                                            b                                        ⁡                                          (                                              x                        ,                        y                        ,                        t                                            )                                                                                  }                        ⋃                          {                                                                    M                    ⁢                                                                                   ⁢                    V                                    _                                ⁢                                  (                                                            x                      -                                              2                        ⁢                        X                                                              ,                                          y                      +                                              2                        ⁢                        Y                                                              ,                                          t                      -                      T                                                        )                                ⁢                .0                            }                                      ⁢                                  ⁢                  where          :                                          ⁢                                                                      U                  _                                b                            ⁡                              (                                  x                  ,                  y                  ,                  t                                )                                      ∈                          {                              0                ,                                  lut                  ⁡                                      (                                                                  (                                                                                                            N                              bl                                                        ⁡                                                          (                                                              x                                ,                                y                                ,                                t                                                            )                                                                                +                          offset                                                )                                            ⁢                      mod                      ⁢                                                                                           ⁢                      p                                        )                                                              }                                                          (        1.35        )                    
Ub(x,y,t) differs from Ua(x,y,t) due to integer offset added to the value of the block rate counter. The estimators a and b are chosen from candidate set to minimize the matching error:                               e          ⁡                      (                                          C                _                            ,              x              ,              y              ,              t                        )                          =                              ∑                          x              ∈                              B                ⁡                                  (                                      x                    ,                    y                    ,                    t                                    )                                                              ⁢                      |                                          F                ⁡                                  (                                      x                    ,                    y                    ,                    t                                    )                                            -                              F                ⁡                                  (                                                            x                      -                                              C                        x                                                              ,                                          y                      -                                              C                        y                                                              ,                                          t                      -                      T                                                        )                                                      |                                              (        1.36        )                            where the matching error is summed over a block B(x,y,t), defined as:B(x,y,t)={(x,y)|Xx−X/2≦x≦Xx+X/2Xy−Y/2≦y≦Xy+Y/2}  (1.37)        
The best of two vectors resulting from estimators a and b is selected in the output multiplexer and assigned to all pixels in B(x,y,t). Good results are obtained from estimators using the ACS strategy where the lut (look up table) containes the following updates:                               U          ⁢                                           ⁢                      S            n                          =                  {                                    (                                                                    0                                                                                        0                                                              )                        ,                          (                                                                    0                                                                                        1                                                              )                        ,                          (                                                                    0                                                                                                              -                      1                                                                                  )                        ,                          (                                                                    0                                                                                        2                                                              )                        ,                          (                                                                    0                                                                                                              -                      2                                                                                  )                        ,                          (                                                                    1                                                                                        0                                                              )                        ,                          (                                                                                          -                      1                                                                                                            0                                                              )                        ,                          (                                                                    3                                                                                        0                                                              )                        ,                          (                                                                                          -                      3                                                                                                            0                                                              )                                }                                    (        1.38        )            
Thus, a new system and method for interlace-to-progressive scan conversion are needed, which implement a new algorithm by an electronic consumer Video Display Processor Chip. The present invention is directed towards meeting this need, among others.